/**
 * 班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。
 * 如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。
 * 给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。
 * 如果 M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。
 * 你必须输出所有学生中的已知的朋友圈总数。
 * 
 * 示例 1:
 * 输入:
 * [[1,1,0],
 * [1,1,0],
 * [0,0,1]]
 * 
 * 输出: 2
 * 说明：已知学生 0 和学生 1 互为朋友，他们在一个朋友圈。 
 * 第 2 个学生自己在一个朋友圈。所以返回 2。
 * 
 * 示例 2:
 * 输入:
 * [[1,1,0],
 * [1,1,1],
 * [0,1,1]]
 * 
 * 输出: 1
 * 
 * 说明：已知学生 0 和学生 1 互为朋友，学生 1 和学生 2 互为朋友，所以学生 0 和学生 2 也是朋友，所以他们三个在一个朋友圈，返回 1。 
 *  [0, 1]
 *  [1, 2]
 *  [2, 1]
 * 
 * 注意：
 * - N 在[1,200]的范围内。
 * - 对于所有学生，有 M[i][i] = 1。
 * - 如果有 M[i][j] = 1，则有 M[j][i] = 1。
 */
// var arr = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]; // 2个朋友圈
// var arr = [[1, 1, 0], [1, 1, 1], [0, 1, 1]]; // 1个朋友圈
var arr = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]; // 3
// var arr = [
//     [1, 1, 0, 0], 
//     [1, 1, 0, 0], 
//     [0, 0, 1, 1],
//     [0, 0, 1, 1]
// ];

/**
 * 解题思想是：
 * 采用DFS深度优先遍历进行解题，将每个学生看作图中的一个节点，求朋友圈数就是求图的强连通分量。
 * 1.首先选取一个节点，开始深度优先搜索，将遍历到的节点标记为visited，直到遍历结束，连通图的数量加1.
 * 2.取另外一个未遍历的节点，重复上述过程。
 * 3.直到所有节点都被遍历。
 * 
 * 
 * 先创建一个代表全员的数组
 * 从第一个开始点亮，朋友圈数量加1, 递归查找朋友，如果找到，将该朋友也点亮
 * 如果遇到点亮的成员，代表已经是某朋友圈的成员
 * 下次循环，只有没有被点亮的，才被当作一个新的朋友圈，再次递归
 * 直到循环结束
 * 
 */
var findCircleNum = function (M) {
    var visited = new Array(M.length).fill(0);
    var res = 0;
    //深度优先遍历
    var dfs = function (i) {
        for (var j = 0; j < M.length; j++) {
            if (i != j && visited[j] != 1 && M[i][j] == 1) {
                visited[j] = 1;
                dfs(j);
            }
        }
    };
    for (var i = 0; i < visited.length; i++) {
        if (visited[i] != 1) {
            visited[i] = 1;
            dfs(i);
            res++;
        }
    }
    return res;
};

console.log(findCircleNum(arr));